package com.dmall.sort.algorithm;

import java.util.Random;

/**
 * 双路快速排序算法
 * 双路快速排序算法可以在任何数组情况下保证算法的时间复杂度为O(nlogn)
 * @author xiao1.wang
 * @date 2021/10/7 22:22
 */
@SuppressWarnings("all")
public class TwoWaysQuickSort implements Sort {
    private static final Random RANDOM = new Random();

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int partition = partition(arr, l, r);
        quickSort(arr, l, partition - 1);
        quickSort(arr, partition + 1, r);
    }

    private int partition(int[] arr, int l, int r) {
        int random = RANDOM.nextInt(r - l + 1) + l;
        swap(arr, random, r);

        // arr[l+1...i-1] <= v; arr[j+1...r] >= v
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i] < arr[l]) {
                i ++;
            }
            while (i <= j && arr[j] > arr[l]) {
                j --;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }

    @Override
    public String getName() {
        return "双路快速排序";
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr);
        Sort sort = new TwoWaysQuickSort();
        sort.sort(arr);
        Sort.printArr(arr);
    }
}
